package algorithm.leetcode;

public class 最长公共前缀 {
    /*
     * 编写一个函数来查找字符串数组中的最长公共前缀。
     * 
     * 如果不存在公共前缀，返回空字符串 ""。
     * 
     * 示例 1:
     * 
     * 输入: ["flower","flow","flight"] 输出: "fl" 示例 2:
     * 
     * 输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。 说明:
     * 
     * 所有输入只包含小写字母 a-z 。
     * 
     * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-common-prefix
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public String longestCommonPrefix(String[] strs) {
        /*
         * 执行用时 : 3 ms , 在所有Java提交中击败了 73.75% 的用户 内存消耗 : 36 MB , 在所有Java提交中击败了
         * 87.63% 的用户
         */
        int len = strs.length;
        if (len == 0) {
            return "";
        }
        Tree prefixTree = buildTree(strs[0], 0);
        for (int i = 1; i < len; i++) {
            prefixTree = findTree(prefixTree, strs[i], 0);
        }
        return transfer(prefixTree);
    }

    String transfer(Tree tree) {
        if (tree == null) {
            return "";
        }
        return tree.ch + transfer(tree.next);
    }

    Tree findTree(Tree tree, String s, int i) {
        if (tree == null) {
            return null;
        }
        if (i >= s.length()) {
            return null;
        }
        if (tree.ch == s.charAt(i)) {
            tree.next = findTree(tree.next, s, i + 1);
            return tree;
        } else {
            return null;
        }
    }

    Tree buildTree(String s, int i) {
        if (i >= s.length()) {
            return null;
        }
        Tree tree = new Tree();
        tree.ch = s.charAt(i);
        tree.next = buildTree(s, i + 1);
        return tree;
    }

    public class Tree {
        char ch;
        Tree next;
    }

    public static void main(String[] args) {
        最长公共前缀 run = new 最长公共前缀();
        String[] strs = { "flower", "flow", "floweht" };
        System.out.println(run.longestCommonPrefix(strs));
    }
}
